The Fast Fourier Transform (FFT) is the generic name for a class of computationally efficient algorithms that implement the Discrete Fourier Transform (DFT) and are widely used in the field of digital signal processing. With the advent of integrated circuits (IC), near real time digital signal processing has become possible. However, circuit designers are still striving for faster and better FFT IC devices.
In a typical computing system, the most time consuming operation is usually associated with memory. This is evident in the many schemes which have been developed to boost memory access time to increase the overall speed of computing systems.
The FFT algorithm is especially memory access and storage intensive. For example, in order to compute a radix-4 DIF FFT butterfly, four pieces of data and three twiddle coefficients are read from memory and four resultant data are written back into memory. In an N-point radix-4 decimation-in-frequency (DIF) FFT, there are a total of 2Nlog.sub.4 N pieces of data and intermediate data to be accessed and stored and a total of (3N/4)log.sub.4 N twiddle coefficients to be accessed. In other words, to compute a 64-point radix-4 DIF FFT, 192 data memory reads and 192 data memory writes and 144 memory reads for the twiddle coefficients must be performed. Accordingly, it is desirable to provide adequate memory arrangement to accommodate all the data and coefficients.
In computing the FFT butterflies going from one rank to the next, the output data of the butterfly computations of the former become the input data of the latter, where the order and grouping of the data vary from one rank to the next. It is therefore necessary to ensure that correct data is accessed from memory for each butterfly computation.
To further increase speed, a fully parallel implementation of an FFT circuit may be desirable. In such a parallel FFT circuit, it is preferable that the four pieces of data and the three twiddle coefficients are available substantially simultaneously for each butterfly computation.
It is apparent from the foregoing that memory access for an FFT circuit is not trivial. Not only a large number of data are accessed from memory, but a large number of resultant data are also stored back into memory for use in future computations. For each butterfly computation, the data and twiddle coefficient must also be obtained substantially simultaneously. Furthermore, for each memory access and storage operation, the address must be correctly computed and referenced.
It is therefore desirable to increase the speed of FFT memory access for the purpose of obtaining and storing FFT computational data and twiddle coefficients. It is further desirable to devise a scheme to access and store the data and twiddle coefficients systematically so that correct data and twiddle coefficients are obtained in a timely fashion for each butterfly computation. In particular, a need has arisen for FFT memory addressing apparatus and method that provides for the above-mentioned desirable features.